// 给定一个包含n + 1个整数的数组nums,里边包含的值都在1~n之间，假设nums中只存在一个重复的整数，要求找出这个重复的数

// 思路1：哈希表
// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(n)

function findRepeatNumber(arr) {
    let set = new Set()
    for (let i = 0; i < arr.length; i++) {
        if (set.has(arr[i])) {
            return arr[i]
        }        
        set.add(arr[i])
    }
    return -1
}

// 思路2：排序后比较
// 时间复杂度：O(nlogn)，n是数组的长度
// 空间复杂度：O(1)

function findRepeatNumber2(arr) {
    arr.sort((a, b) => a - b)
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== i + 1) {
            return arr[i]
        }        
    }
    return -1
}

let arr = [1, 3, 2, 2, 4]
console.log(findRepeatNumber(arr))

let arr2 = [1, 3, 2, 2, 4]
console.log(findRepeatNumber2(arr2))